import com.sun.org.apache.bcel.internal.generic.DADD;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 74646
 * Date: 2022-02-07
 * Time: 10:48
 */
class ListNode{
    public int val;
    //prev 存放前一个结点的地址
    public ListNode prev;
    //next 存放后一个结点的地址
    public ListNode next;
    public ListNode(int val){
        this.val = val;
    }
}

public class MyLinkedList {
    public ListNode head = new ListNode(-1);
    public ListNode last;

    //打印链表
    public void display(){
        ListNode cur = this.head.next;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    //得到单链表的长度
    public int size(){
        ListNode cur = this.head.next;
        int count = 0;
        while (cur!=null){
            count ++;
            cur = cur.next;
        }
        return count;
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        if(head.next == null) return false;
        ListNode cur = this.head.next;
        while (cur!=null){
            if(cur.val==key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //头插法
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        if(this.head.next==null){
            this.head.next = node;
            this.last = node;
        }else {
            node.next = head.next;
            head.next = node;
            node.prev = head;
        }
    }

    //尾插法
    public void addLast(int data){
        ListNode node = new ListNode(data);
        if(this.head.next==null){
            this.head.next = node;
            this.last = node;
        }else {
            this.last.next = node;
            node.prev = this.last;
            this.last = node;
        }
    }

    //删除第一次出现关键字为key的节点
    public void remove(int key){
        ListNode cur = this.head.next;
        while (cur!=null){
            if(cur.val==key){
                //删除第一结点
                if(cur == this.head.next){
                    head.next = cur.next;
                    if(head.next!=null){
                        cur.next.prev = head;
                    }else {
                        this.last = null;
                    }
                } else{
                    //删除中间结点
                    if(cur.next!=null){
                        cur.prev.next = cur.next;
                        cur.next.prev = cur.prev;
                    }else{
                        cur.prev.next = cur.next;
                        last = last.prev;
                    }
                }
                return;
            }
            cur = cur.next;
        }
        System.out.println("没有要删除的结点");
    }

    //删除所有值为key的节点
    public void removeAllKey(int key){
        ListNode cur = this.head.next;
        while (cur!=null){
            if(cur.val==key){
                //删除第一个结点
                if(cur == this.head.next){
                    this.head.next = cur.next;
                    if(this.head.next!=null){
                        cur.prev = head;
                    }else {
                        this.last = null;
                    }
                }else {
                    cur.prev.next = cur.next;
                    if(cur.next!=null){
                        cur.next.prev = cur.prev;
                    }else {
                        last = last.prev;
                    }
                }
            }
            cur = cur.next;
        }
    }

    //找到 index 的位置
    public ListNode searchIndex(int index){
        ListNode cur = this.head;
        while (index!=0){
            cur = cur.next;
            index--;
        }
        return cur;
    }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
        if(index<0 || index>size()){
            System.out.println("插入位置不合法");
            return;
        }
        if(index==0){
            addFirst(data);
            return;
        }
        if(index==size()){
            addLast(data);
            return;
        }
        ListNode node = new ListNode(data);
        ListNode cur = searchIndex(index);
        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;
    }

    //清空链表
    public void clear(){
        ListNode cur = this.head.next;
        while (cur!=null){
            ListNode curNext = cur.next;
            cur.prev = null;
            cur.next = null;
            cur = curNext;
        }
        this.head.next = null;
        this.last = null;
    }
}


//    public ListNode head; //指向双向链表的头结点
//    public ListNode last; //指向双向链表的尾巴结点
//
//    //打印链表
//    public void display(){
//        //与单链表的打印方式一样
//        ListNode cur = this.head;
//        while (cur!=null){
//            System.out.print(cur.val+" ");
//            cur = cur.next;
//        }
//        System.out.println();
//    }
//    //得到单链表的长度
//    public int size(){
//        ListNode cur = this.head;
//        int count = 0;
//        while (cur!=null){
//            count ++;
//            cur = cur.next;
//        }
//        return count;
//    }
//    //查找是否包含关键字key是否在单链表当中
//    public boolean contains(int key){
//        if(head == null) return false;
//        ListNode cur = this.head;
//        while (cur!=null){
//            if(cur.val==key){
//                return true;
//            }
//            cur = cur.next;
//        }
//        return false;
//    }
//    //头插法
//    public void addFirst(int data){
//        ListNode node = new ListNode(data);
//        if(this.head==null){
//            this.head = node;
//            this.last = node;
//        }else {
//            node.next = this.head;
//            head.prev = node;
//            this.head = node;
//        }
//    }
//    //尾插法
//    public void addLast(int data){
//        ListNode node = new ListNode(data);
//        if(this.head==null){
//            this.head = node;
//            this.last = node;
//        }else {
//            this.last.next = node;
//            node.prev = this.last;
//            this.last = node;
//        }
//    }
//    //删除第一次出现关键字为key的节点
////    public void remove(int key){
////        ListNode cur = head;
////        while (cur!=null){
////            if(cur.val==key){
////                //删除头结点
////                if(cur==head){
////                    head = head.next;
////                    head.prev = null;
////                }else {
////                    cur.prev.next = cur.next;
////                    //删除中间结点
////                    if(cur.next!=null){
////                        cur.next.prev = cur.prev;
////                    }else {
////                        //删除尾巴结点
////                        last = last.prev;
////                    }
////                }
////                return;
////            }
////                cur = cur.next;
////        }
////        System.out.println("没有要删除的结点");
////    }
//    public void remove(int key){
//        ListNode cur = head;
//        while (cur!=null){
//            if(cur.val==key){
//                //删除头结点
//                if(cur==head){
//                    head = head.next;
//                    if(head!=null){
//                        head.prev = null;
//                    }else {
//                        last = null;
//                    }
//                }else {
//                    //删除尾巴结点
//                    if(cur==last){
//                        cur.prev.next = cur.next;
//                        last = last.prev;
//                    //删除中间结点
//                    }else {
//                        cur.prev.next = cur.next;
//                        cur.next.prev = cur.prev;
//                    }
//                }
//                return;
//            }
//                cur = cur.next;
//        }
//        System.out.println("没有要删除的结点");
//    }
//
//    //删除所有值为key的节点
//    public void removeAllKey(int key){
//            ListNode cur = head;
//            while (cur!=null){
//                if(cur.val==key){
//                    //删除头结点
//                    if(cur==head){
//                        head = head.next;
//                        if(head!=null){
//                            head.prev = null;
//                        }else {
//                            last = null;
//                        }
//                    }else {
//                        //删除尾巴结点
//                        if(cur==last){
//                            cur.prev.next = cur.next;
//                            last = last.prev;
//                        //删除中间结点
//                        }else {
//                            cur.prev.next = cur.next;
//                            cur.next.prev = cur.prev;
//                        }
//                    }
//                }
//                cur = cur.next;
//            }
//        }
//
//    //找到 index 的位置
//    public ListNode searchIndex(int index){
//        ListNode cur = head;
//        while (index!=0){
//            cur = cur.next;
//            index--;
//        }
//        return cur;
//    }
//    //任意位置插入,第一个数据节点为0号下标
//    public void addIndex(int index,int data){
//        if(index<0||index>size()){
//            System.out.println("插入位置不合法");
//            return;
//        }
//        //头插
//        if(index==0){
//            addFirst(data);
//            return;
//        }
//        //尾插
//        if(index==size()){
//            addLast(data);
//            return;
//        }
//        ListNode node = new ListNode(data);
//        ListNode cur = searchIndex(index);
//        node.next = cur;
//        cur.prev.next = node;
//        node.prev = cur.prev;
//        cur.prev = node;
//    }
//
//    //清空链表
//    public void clear(){
////        this.head = null;
////        this.last = null;
//        while (head!=null){
//            ListNode curNext = head.next;
//            head.prev = null;
//            head.next = null;
//            head = curNext;
//        }
//        last = null;
//    }
//}
